\extitle{3}{原根与同余方程}


\section{群及元素的阶}




\begin{exercise}
证明 $\mathbb{Z}$ 是加法循环群， 可能的生成元有哪些?
\end{exercise}

\begin{solution}
  显然$\ZZ$对加法封闭，且加法满足结合律、交换律；
  显然零元素正是$0$, $n$的负元为$-n$;
  因此$\ZZ$为加法群。
  对整数$n$, $\pm n$生成的加法子群为
  \[
    n\ZZ=\{\cdots, -2n, -n, 0, n, 2n, \cdots\}.
  \]
  这样$\pm 1$生成$\ZZ$, $\ZZ$为$\pm 1$生成的循环群。 
  若$|n|>1$或$n=0$, 则显然$n\ZZ$中没有$1$, 故$n$不能生成$\ZZ$.
  由此，可能的生成元只有$\pm 1$.
\end{solution}

\begin{exercise}
证明 $\mathbb{Z} / m \mathbb{Z}$ 是加法循环群， 可能的生成元有哪些?
\end{exercise}

\begin{solution}
  $\ZZ/m\ZZ$是由$\bar{1}$生成的加法循环群。可能的生成元只有$\pm 1$.
\end{solution}

\begin{exercise}
求如下乘法群所有元素的阶： $(\mathbb{Z} / 6 \mathbb{Z})^{*},(\mathbb{Z} / 8 \mathbb{Z})^{*},(\mathbb{Z} / 10 \mathbb{Z})^{*},(\mathbb{Z} / 16 \mathbb{Z})^{*}$.
\end{exercise}

\begin{solution}
  令$U_m=(\ZZ/m\ZZ)^*$. 我们有$\# U_m=\varphi(m)$. 令$\bar{a}\in U_m$.
  注意到如下事实：
  \begin{enumerate}[(i)]
    \item $\ord_{m}(a)=1$当且仅当$a\equiv 1\left( \mod m \right)$;
    \item 对$m>2$, $\ord_m(-1)=2$.
    \item  $\ord_m(a)\mid \varphi(m)$;
    \item $\ord_{m}(a^k)=\frac{\ord_m(a)}{(k, \ord_m(a))}$;
    \item $\ord_{m}(a^{-1})=\ord_{m}(a)$.
    \end{enumerate}
  下面计算中我们应用了这些事实。
  \begin{enumerate}
    \item $U_6=\{\bar{1}, \bar{5}\}$, $\ord_{6}(a) \mid 2$. 我们有
        $\ord_6(1)=1, \ord_6(5)=2.$
      \item $U_{8}=\{\bar{1}, \bar{3}, \bar{5}, \bar{7}\}$, $\ord_{8}(a) \mid 4$. 我们有$\ord_{8}(1)=1$, $\ord_8(3)=\ord_8(5)=\ord_8(7)=2$.
      \item $U_{10}=\{\bar{1}, \bar{3}, \bar{7}, \bar{9}\}$, $\ord_{10}(a) \mid 4$. 我们有
      \begin{enumerate}[(a)]
          \item $\ord_{10}(1)=1$;
            \item $\ord_{10}(3)\neq 2$, 故$\ord_{10}(3)=4$;
              \item $\ord_{10}(7)=\ord_{10}(3^{-1})=\ord_{10}(3)=4$;
                \item $\ord_{10}(9)=\ord_{10}(3^2)=\frac{\ord_{10}(3)}{(2, \ord_{10}(3))}=2$.
              \end{enumerate}
            \item $U_{16}=\{\bar{1}, \bar{3}, \bar{5}, \bar{7}, \bar{9}, 
              \overline{11}, \overline{13}, \overline{15}\}$, 
              $\ord_{16}(a) \mid 8$. 我们有
      \begin{enumerate}[(a)]
\item $\ord_{16}(1)=1$;
\item $3^2\equiv 9\left( \mod 16 \right)$, $3^4\equiv 1\left( \mod 16 \right)$, 故$\ord_{16}(3)=4$;
\item $5^2\equiv 9\left( \mod 16 \right)$, $5^4\equiv 9\cdot 9\equiv  1\left( \mod 16 \right)$, 故$\ord_{16}(5)=4$;
  \item $7^2\equiv 1\left( \mod 16 \right)$, 故$\ord_{16}(7)=2$;
    \item $\ord_{16}(9)=\ord_{16}(3^2)=\frac{\ord_{16}(3)}{(2, \ord_{10}(3))}=2$.
      \item $\ord_{16}(11)=\ord_{16}(3^{-1})=\ord_{16}(3)=4$;
        \item $\ord_{16}(13)=\ord_{16}(5^{-1})=\ord_{16}(5)=4$;
          \item $\ord_{16}(15)=\ord_{16}(-1)=2$.
        \end{enumerate}
  \end{enumerate}
  为了清楚地展示，我们用表格表示这些阶：
  \begin{center}
    \begin{tabular}[]{C||C|C|C||C|C|C}
      \hline
       \ord_6(5) & 
       \ord_8(3) & \ord_8(5) & \ord_8(7) & 
       \ord_{10}(3) & \ord_{10}(7) & \ord_{10}(9) \\
       \hline
2 & 2 & 2 & 2 & 4 & 4& 2  \\
\hline\hline
\ord_{16}(3) &  \ord_{16}(5) &  \ord_{16}(7) &  \ord_{16}(9) &  \ord_{16}(11) &  \ord_{16}(13) &  \ord_{16}(15) \\
\hline
4& 4 & 2& 2& 4& 4& 2\\
\hline
    \end{tabular}
  \end{center}
\end{solution}

\begin{exercise}
若群 $G$ 的元素 $x$ 均满足 $x^{2}=1$, 证明： $G$ 为 Abel 群。
\end{exercise}

\begin{solution}
  令$x, y\in G$. 那么$x^2=y^2=(xy)^2=1$.
  从而
  \[
    x^{-1}=x,\quad y^{-1}=y,\quad  1=xyxy=xyx^{-1}y^{-1},
  \]
  因此$xy=yx$. 这样$G$ 为 Abel 群。 
\end{solution}

\begin{exercise}\label{循环群的子群结构}
设 $G=\langle g\rangle$ 为 $n$ 阶 (乘法)循环群。 证明： 若 $d$ 是 $n$ 的正因子， 
则 $\left\langle g^{n / d}\right\rangle$ 是 $G$ 的 $d$ 阶子群; 且是唯一的 $d$ 阶子群。
\end{exercise}

\begin{solution}
  由引理5知$\ord(g^{\frac{n}{d}})=\frac{n}{(n,\frac{n}{d})}=d$. 故
$\left\langle g^{n / d}\right\rangle$ 是 $G$ 的 $d$ 阶子群。要证明$d$阶子群的唯一性，
我们有如下两种方法。


\fangfa{1} 若 \(H\) 是 \(G\) 的 \(d\) 阶子群，记 \(S = \left\{  {i \in  \mathbb{Z} \mid  {g}^{i} \in  H}\right\}\).
$g^i\in H$蕴含$g^{-i}\in H$, 且$g^i,g^j\in H$蕴含${g}^{i}{g}^{j} = {g}^{i + j}$,
因此$S$对取负元和求和封闭，这样
\(S\) 为 \(\mathbb{Z}\) 的加法子群。
令\(\delta\) 为 \(S\) 中最小正整数，我们断言 \(S = \delta \mathbb{Z}\).
诚然，对任意 \(s \in  S\), 设\(s = {\delta q} + r,0 \leqslant  r < \delta\),
则 $r = s - {\delta q} \in  S$. 而$0 \leqslant  r < \delta$,
由$\delta$的最小性知$r=0$, 故$\delta  \mid  s$.
得证断言。
既然 \(S = \langle \delta \rangle\),
\(H = \left\langle  {g}^{\delta }\right\rangle\). 因 \({g}^{n} = 1 \in  H\),故 \(n \in  S,\delta  \mid  n\). 
从而 \(H = \left\langle  {g}^{\delta }\right\rangle\) 的阶 \(d\) 实为 \(n/\delta\), 
故 \(\delta  = n/d\), \(H = \left\langle  {g}^{n/d}\right\rangle\).

  \fangfa{2} 我们可等同$G$与
  $\CC^*$的乘法子群$W_n=\{1,\zeta_n,\cdots,\zeta_n^{n-1}\}$, 
其中$\zeta_n=e^{\frac{2\pi i}{n}}$. 令$H$为$G$的一个$d$阶子群。
  那么对任意的$a\in H$, $a^d=1$.
  因此$H$恰为$x^d-1$的根集。这就证明$d$阶子群的唯一性。
\end{solution}

\begin{exercise}
求乘法群 $W_{n}=\{1, \mathrm{i},-1,-\mathrm{i}\}$ 的所有子群 $H$, 对 $H$ 的陪集分解， $H$ 的指数。
\end{exercise}

\begin{solution}
$W_n$为有限循环群，
由练习~\ref{循环群的子群结构}~知$W_n$的子群都是循环群。
所有子群为
\[
  H_1=\pair{1}=\{1\},\quad H_2=\pair{-1}=\{1,-1\},\quad
  H_3=\pair{i}=\pair{-i}=W_n.
\]
$W_n$对$H_1, H_2, H_3$的(左)陪集分解分别为
\[
\begin{aligned}
  W_n&= H_1\sqcup i H_1\sqcup (-1) H_1\sqcup (-i)H_1,\\
  W_n&= H_2\sqcup i H_2,\\
  W_n&= H_3.
\end{aligned}
\]
$H_1, H_2, H_3$ 的指数分别为$4,2,1$.
\end{solution}

\begin{exercise}
求乘法群 $W_{n}=\left\{1, \zeta_{n}, \zeta_{n}^{2}, \cdots, \zeta_{n}^{n-1}\right\}$ 的所有子群及其指数。
\end{exercise}

\begin{solution}
  由练习~\ref{循环群的子群结构}~知：对每个$d\mid n$,
  $W_n$恰好有一个的$d$阶子群$H_d=\pair{\zeta_n^{\frac{n}{d}}}$.
  $H_d$的指数为$\frac{n}{d}$.
\end{solution}

\begin{exercise}
  设$n\geqslant 2$. 证明： $n \nmid 2^{n}-1$.
\end{exercise}

\begin{solution}
若$n$为偶数，显然$n\nmid 2^n-1$. 可设$n$为奇数。
令 \(p\) 是 \(n\) 的最小素因子， \(n = {p}^{k}{n}_{1}\), 其中 \(p \nmid  {n}_{1}\). 
由于$\ord_p(2)\mid (p-1)$, $\ord_p(2)$的任一素因子小于$n$的任一素因子。
如此，$\ord_p(2)\nmid n$.
从而
${2}^{n} \nequiv 1\left(  \mod p\right).$
亦即，$p\nmid 2^n-1$. 故$n\nmid 2^n-1$.
\end{solution}

\begin{exercise}
设 $m, n$ 互素， 证明： $2^{m}-1$ 与 $2^{n}-1$ 互素。
\end{exercise}

\begin{solution}
  \fangfa{1}
  记 \(d = \left( {{2}^{m} - 1,{2}^{n} - 1}\right)\). $d$ 为奇数，故 \(2 \in  {U}_{d} = {\left( \mathbb{Z}/d\mathbb{Z}\right) }^{ * }\).
  令$k=\ord_d(2)$. 
因 \({2}^{m} \equiv  1\left( {\mod d}\right)\),故 \(k \mid  m\); 同理 \(k \mid  n\). 故
$k = 1$, 这样 $2 \equiv  1 \left( {\mod d}\right)$,
即 \(d \mid  \left( {2 - 1}\right)  = 1\),故 \(d = 1\).

\fangfa{2} 在习题1.2的第7题中我们计算出了$(2^m-1,2^n-1)=2^d-1$, 其中$d=(m,n)$.
\end{solution}

\begin{exercise}\label{1/a的循环节长度}
\begin{enumerate}[(1)]
\item 用除法（竖算式）逐步求出 $\frac{1}{7}=0 . \overline{142857}$ (横线下是循环数字).

\item%(2)
对$k=1,2,3, \cdots$逐步求出 $10^{k} \equiv r_{k} \left(\mod 7\right)$ ($0 \leqslant r_{k}<7$).

\item%(3)
上述 (1) 和 (2) 有何联系?
\end{enumerate}
\end{exercise}

\begin{solution}
\begin{enumerate}
  \item 略。
  \item 注意到$\ord_{7}(10)=6$. 进而易知
    \[
      r_k=\begin{cases}
        3, & \text{若$k\equiv 1\left( \mod 6 \right)$};\\
2, & \text{若$k\equiv 2\left( \mod 6 \right)$};\\
6, & \text{若$k\equiv 3\left( \mod 6 \right)$};\\
4, & \text{若$k\equiv 4\left( \mod 6 \right)$};\\
5, & \text{若$k\equiv 5\left( \mod 6 \right)$};\\
1, & \text{若$k\equiv 6\left( \mod 6 \right)$}.\\
      \end{cases}
    \]
  \item 
  竖算式实为 
  \[
  \begin{aligned}
    1\times {10} &=  7\times  1  + 3, & 3\times {10} &=  7\times 4  + 2, & 
    2\times 10&= 7\times 2 + 6,\\
    6\times 10&= 7\times 8 + 4, & 4\times 10&= 7\times 5+5, &
    5\times 10&= 7\times 7+1, \\
    1\times {10} &=  7\times  1  + 3,  & \cdots
  \end{aligned}
\]
一般地，若\((m,10)=1\), 则
\(1/m\) 的小数展开周期等于 $10\left( \mod m \right)$ 的阶。
\qedhere
%诚然，令$k=\ord_m(10)$. 
\end{enumerate}
\end{solution}

\begin{exercise}
\starmark
设 $n, a$ 为整数， $n>0$, 证明：
\[
  \sum_{x} e^{\frac{2 \pi \mathrm{i}ax }{ n}}=\sum_{x} \zeta_{n}^{a x}= \begin{cases}0, & \text { 若~} a \neq 0 \left(\mod n\right), \\ n, & \text { 若~} a \equiv 0 \left(\mod n\right),\end{cases}
\]
其中求和指标$x$ 遍历模 $n$ 的完全剩余系。
\end{exercise}

\begin{solution}
若 \(a \equiv  0\left( {\mod n}\right) ,{\zeta }_{n}^{a} = 1\),故 \(\mathop{\sum }\limits_{x}{\zeta }_{n}^{ax} = n\). 若 \(a ≢ 0\left( {\mod n}\right)\),则 \({\zeta }_{n}^{a} \neq  1\). 记 \(r\) 为 \(x\) 模 \(n\) 的最小非负剩余，则 
\[
\sum _{x}{\zeta }_{n}^{ax} = \sum_{{r = 0}}^{{n - 1}}{\left( {\zeta }_{n}^{a}\right) }^{r} = \frac{{\left( {\zeta }_{n}^{a}\right) }^{n} - 1}{{\zeta }_{n}^{a} - 1} = 0.
\]
\end{solution}



\begin{exercise}
\starmark
设 $a$ 为整数， 证明：
\[
  \int_{0}^{1} e^{2 \pi \mathrm{i} a x} \mathrm{~d} x= \begin{cases}0, & \text { 若~} a \neq 0, \\ 1, & \text { 若~} a=0. \end{cases}
\]
\end{exercise}

\begin{solution}
若 \(a = 0\),则 \({\mathrm{e}}^{2\pi iax} = 1\),故其积分为 $1$. 若 \(a \neq  0\),则
\[
{\int }_{0}^{1}{\mathrm{e}}^{{2\pi }\mathrm{i}{ax}}\mathrm{\;d}x = {\int }_{0}^{1}\cos \left( {2\pi ax}\right) \mathrm{d}x + \mathrm{i}{\int }_{0}^{1}\sin \left( {2\pi ax}\right) \mathrm{d}x = 0.
\]
\end{solution}

\begin{exercise}
设 $G, G^{\prime}$ 是两个 Abel 加法群， 映射 $\sigma: G \rightarrow G^{\prime}$ 是群的同态映射， 记
\[
\operatorname{ker} \sigma=\{a \in G \mid \sigma(a)=0\}
\]
(称为 $\sigma$ 的核). 则 $\operatorname{ker} \sigma$ 是子群， 可将 $G$ 的元素分类： $a, a^{\prime}$ 同类当且仅当 $a-a^{\prime} \in \operatorname{ker} \sigma, a$
所在的类记为 $\bar{a}=a+\operatorname{ker} \sigma$. 所有类 (模 $\operatorname{ker} \sigma$ 同余类)的集合记为
\[
G / \operatorname{ker} \sigma=\{\bar{a} \mid a \in G\},
\]
定义 $\bar{a}+\bar{b}=\overline{a+b}$, 则 $G / \operatorname{ker} \sigma$ 是 Abel 群， 称为 $G$ 模 $\operatorname{ker} \sigma$ 的商群。 再证明：
\[
G / \operatorname{ker} \sigma \cong \operatorname{Im} \sigma, \quad \bar{a} \mapsto \sigma(a)
\]
(群同态基本定理)，其中 $\operatorname{Im} \sigma=\{\sigma(a) \mid a \in G\} \subset G^{\prime}$. 最后举出一例。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
设 $G, G^{\prime}$ 是两个 Abel 乘法群， 试映射 $\sigma: G \rightarrow G^{\prime}$ 是群的同态映射。 定义 $\operatorname{ker} \sigma$, 并叙述和证明群同态基本定理。 举出一例。
\end{exercise}

\begin{solution}

\end{solution}


\section{模 $p^{s}$ 原根}



\begin{exercise}
试求模 $m=7,11,13,17,19$ 的所有原根， 并列表将$U_m$中元素表为最小原根的幂。
\end{exercise}

\begin{solution}
  我们应用如下结论：若$(g,m)=1$, $\varphi(m)$的全部素因子为$p_1,\cdots,p_t$, 
  则$g$为模$m$原根当且仅当$g^{\frac{\varphi(m)}{p_i}}\nequiv 1\left( \mod m \right)$, 对任意$i$.
  \begin{enumerate}
    \item $\varphi(7)=6=2\cdot 3$. $7/2=3, 7/3=2$. 我们逐个对$2\leqslant g<7$试验，至到找到一个原根。

      $g=2$非原根，因为$2^3\equiv 1\left( \mod 7 \right)$. 

      $g=3$为原根，因为$3^2\equiv 2\left( \mod 7 \right), 3^3\equiv -1\left( \mod 7 \right)$. 

      这样找到了最小原根$3$. 所有原根为
      \[
        \{3^k\mid (k, 6)=1, 1\leqslant k< 6\}=\{3, 3^5\}\equiv \{3, 3^{-1}\}\equiv \{3, 5\} \left( \mod 7 \right).
      \]
    \item $\varphi(11)=10=2\cdot 5$. $10/2=5, 10/5=2$. 我们逐个对$2\leqslant g<11$试验，至到找到一个原根。

      $g=2$为原根，因为$2^2\equiv 4\left( \mod 11 \right)$, $2^5\equiv -1\left( \mod 11 \right)$. 

      这样找到了最小原根$2$. 原根$\bar{2}$如下生成$U_{11}$:
\begin{center}
        \begin{tabular}{C|C|C|C|C|C|C|C|C|C}
          \hline
        2^0 & 2^1 & 2^2 & 2^3 & 2^4 & 2^5 & 2^6 & 2^7 & 2^8 & 2^9 \\
        \hline
        1 & 2 & 4 & 8 & 5 & 10 & 9 & 7 & 3 & 6 \\
        \hline
        \end{tabular}
    \end{center}
      (手算时注意到：把$2^i$除以$11$的余数$r$算出来后，$2^{i+1}$除以$11$的余数为$2\times r$除以$11$的余数。)

      所有原根为
      \[
        \{2^k\mid (k, 10)=1, 1\leqslant k< 10\}=\{2, 2^3, 2^7, 2^9\}\equiv \{2, 8, 7, 6\} \left( \mod 11 \right).
      \]
    \item $\varphi(13)=12=2^2\cdot 3$. $12/2=6, 12/3=4$. 我们逐个对$2\leqslant g<13$试验，至到找到一个原根。

      $g=2$为原根，因为$2^4\equiv 3\left( \mod 13 \right)$, $2^6\equiv -1\left( \mod 13 \right)$. 

      这样找到了最小原根$2$. 所有原根为
      \[
        \{2^k\mid (k, 12)=1, 1\leqslant k< 12\}=\{2, 2^5, 2^7, 2^{11}\}\equiv \{2, 6, 11, 7\} \left( \mod 13 \right).
      \]
    \item $\varphi(17)=16=2^4$. $16/2=8$. 我们逐个对$2\leqslant g<17$试验，至到找到一个原根。

      $g=2$非原根，因为$2^8\equiv 1\left( \mod 17 \right)$. 

      $g=3$为原根，因为$3^8\equiv -1\left( \mod 17 \right)$. 

      这样找到了最小原根$3$. 所有原根为
      \[
      \begin{aligned}
              \{3^k\mid (k, 16)=1, 1\leqslant k< 16\}&= \{3, 3^3, 3^5, 3^7, 3^9, 3^{11}, 3^{13}, 3^{15}\}\\
                    &\equiv  \{3, 10, 5, 11, 14, 7, 12, 6\} \left( \mod 17 \right).
                  \end{aligned}
    \]
    \item $\varphi(19)=18=2\cdot 3^2$. $18/2=9, 18/3=6$. 我们逐个对$2\leqslant g<19$试验，至到找到一个原根。

      $g=2$为原根，因为$2^9\equiv -1\left( \mod 19 \right)$, $2^6\equiv 4\left( \mod 19 \right)$. 

      这样找到了最小原根$2$. 原根$\bar{2}$如下生成$U_{19}$:
      \begin{center}
        \begin{tabular}{C|C|C|C|C|C|C|C|C}
          \hline
        2^0 & 2^1 & 2^2 & 2^3 & 2^4 & 2^5 & 2^6 & 2^7 & 2^8 \\
        \hline
        1 & 2 & 4 & 8 & 16 & 13 & 7 & 14 & 9 \\
        \hline\hline
2^9 & 2^{10} & 2^{11} & 2^{12} & 2^{13} & 2^{14} & 2^{15} & 2^{16} & 2^{17}\\
\hline
18 & 17 & 15 & 11 & 3 & 6 & 12 & 5 & 10\\
\hline
        \end{tabular}
      \end{center}
      所有原根为
      \begin{align*}
      \{2^k\mid (k, 18)=1, 1\leqslant k< 18\}&= \{2, 2^5, 2^7, 2^{11}, 2^{13}, 2^{17}\}\\
            & \equiv \{2, 13, 14, 15, 3, 10\} \left( \mod 19 \right).
            \tag*{\qedhere}
          \end{align*}
  \end{enumerate}
\end{solution}

\begin{exercise}
试求模 $41$ 的所有原根。
\end{exercise}

\begin{solution}
  $\varphi(41)=40=2^3\times 5$. 对于$2\leqslant g<41$, 
  我们通过确定$g^{20}, g^{8}\nequiv 1\left( \mod 41 \right)$找到最小的原根$g$.
\begin{enumerate}
  \item 试$2$. $2$非原根, 因为
    \[
    \begin{aligned}
2^{20}& \equiv 2^{6\cdot 3+2}\equiv 23^3\times 4 \equiv 37\times 23\times 4
    \equiv 1\left( \mod 41 \right).
  \end{aligned}
  \]
  \item 试$3$. $3$非原根, 因为
    \[
    \begin{aligned}
      3^{8}& \equiv 81^2 \equiv (-1)^2
    \equiv 1\left( \mod 41 \right).
  \end{aligned}
  \]
\item 跳过$4=2^2$. $2$非原根，$4=2^2$更不是。这是因为$\ord(4)=\frac{\ord(2)}{(2,\ord(2))} \leqslant \ord(2)$.
\item 试$5$. $5$非原根, 因为
    \[
    \begin{aligned}
      5^{20}& \equiv 5^{3\times 6+2}\equiv 125^6\cdot 25 \equiv 2^6\cdot 25\equiv 23\times 25
    \equiv 1\left( \mod 41 \right).
  \end{aligned}
  \]
\item 试$6$. $6$确为原根，因为
  \[
    \begin{aligned}
      6^{8} & \equiv 6^{2\times 4}\equiv (-5)^4\equiv 125\cdot 5\equiv 2\times 5\equiv 10 \left( \mod 41 \right),\\
      6^{20} & \equiv 6^{2\times 8+ 2\times 2}\equiv 10^2\times (-5)^{2} \equiv 2500 \equiv 40 \left( \mod 41 \right).
    \end{aligned}
  \]
\end{enumerate}
如此，我们找到了最小的原根$6$. 所有的模$41$原根为
\[
\begin{aligned}
  &\hspace{1.3em} \{6^k\mid (k,40)=1, 1\leqslant k<40\} \\
  &=  \{6, 6^3, 6^7, 6^9, 6^{11}, 6^{13}, 6^{17}, 6^{19}, 6^{21}, 6^{23},
  6^{27}, 6^{29}, 6^{31}, 6^{33}, 6^{37}, 6^{39}\}\\
  &\equiv \{6, 11, 6^8\cdot 6^{-1}, 6^8\cdot 6^3, \cdots \}\\
  & \equiv \{6, 11, 10\cdot 7, 10\cdot 11, \cdots\}\\
  &\equiv \{6, 11, 29, 19, 28, 24, 26, 34, 35, 30, 12, 22, 13, 17, 15, 7\} \left( \mod 41 \right).
\end{aligned}
\]
总共有$\varphi(\varphi(41))=16$个。
\end{solution}

\begin{exercise}
试求模 $m=41^{2}$ 和 $2 \cdot 41^{2}$ 的所有原根。（求出一个具体的原根，再描述全部的原根。）
\end{exercise}

\begin{solution}
  我们应用系1. 
  由上一题我们易知模$41$最小原根为$6$. 由于$6^{40}\equiv 124\nequiv 1\left( \mod 41^2 \right)$,
  $6$为模$41^2$原根。进而$6+41^2=1687$为模$2 \cdot 41^{2}$ 原根。

  既得一个原根，我们可给出所有原根。我们有$\varphi(41^2)=\varphi(2\cdot 41^2)=1640$. 
模 $41^{2}$ 和 $2 \cdot 41^{2}$ 的所有原根分别为
\[
    \{6^k\mid (k, 1640)=1, 1\leqslant k<1640\}, 
    \quad
    \{1687^k\mid (k, 1640)=1, 1\leqslant k<1640\},
\]
个数都是$\varphi(1640)=640$.
\end{solution}

\begin{exercise}
设$p$ 为奇素数， $a$ 为模 $p^{k}$ 原根， 证明 $a$ 也是模 $p$ 原根。
\end{exercise}

\begin{solution}
  按照假定$p$ 为奇素数。
  若$a\equiv 1\left( \mod p \right)$, 则$a=1+cp$, 对某个整数$c$. 由引理1(2)知
  \[
    a^{p^{k-1}}=(1+cp)^{p^{k-1}}\equiv 1\left( \mod p^k \right).
  \]
  故$a$非模$p^k$原根 ($a$为模$p^k$原根相当于$\operatorname{ord}_{p^k} (a)=\varphi(p^k)=p^{k-1}(p-1)$).
  这样$a$为模$p^k$原根时$a\nequiv 1\left( \mod p \right)$. 

  我们反证得到$a$ 为模 $p^{k}$ 原根时亦为模 $p$ 原根。
  令$g$为模$p$原根。令$a\equiv g^d\left( \mod p \right)$, 其中$d\in \{0,1,\cdots,p-1\}$. 
  那么$d\neq 0$. 
  若$a$非模$p$原根，则 $d>1$且$d\mid (p-1)$. 
  设$a=g^d+cp$, 令$e=\frac{p-1}{d}$. 
  我们有
  \[
    a^{e}\equiv (g^d)^e\equiv 1\left( \mod p \right).
  \]
  可令$a^e=1+tp$.  
  由引理1(2)知
  \[
    a^{ep^{k-1}} \equiv (1+tp)^{p^{k-1}}\equiv 1+tp^{k}\left( \mod p^{k+1} \right),
  \]
  从而
  \[
    a^{ep^{k-1}} \equiv 1\left( \mod p^k \right).
  \]
  这样$\operatorname{ord}_{p^k} (a)\mid ep^{k-1}$. 特别地，
  $\operatorname{ord}_{p^k} (a) < p^{k-1}(p-1)$. 这与$a$为模$p^k$原根相矛盾。
  因此$a$必为模$p$原根。
\end{solution}

\begin{exercise}
设素数 $p=4 s+1$, 证明： $a$ 为模 $p$ 原根当且仅当 $-a$ 是。
\end{exercise}

\begin{solution}
  只用证明($\Rightarrow$), 之后交换$a, -a$的角色可得($\Leftarrow$).
  若$a$为模 $p$ 原根，则
  $\operatorname{ord}(\bar{a})=p-1=4s$. 
  从而$a^{2s}\equiv -1\left( \mod p \right)$. 
  因此$a^{2s+1}\equiv -a\left( \mod p \right)$.
  因为
  \[
    (2s+1, p-1)=(2s+1, 4s)=(2s+1,-2)=1,
  \]
  所以
  \[\ord_{p}(-a)=\ord_p(a^{2s+1})=\frac{\ord_p(a)}{(2s+1, \ord_p(a))}=\ord_p(a).\]
  于是$-a$也是模$p$ 原根。
\end{solution}

\begin{exercise}
若正整数 $a, m$ 互素， 证明： $a^{i} \equiv a^{j} \left(\mod m\right)$ 当且仅当 $i \equiv j\left(\mod \operatorname{ord}_{m} a\right)$ (这里 $i, j$ 为非负整数).
\end{exercise}

\begin{solution}
  $a^{i} \equiv a^{j} \left(\mod m\right)$ 当且仅当 $a^{i-j}\equiv 1\left( \mod m \right)$, 当且仅当
  $\ord_m(a)\mid (i-j)$,
  当且仅当 $i \equiv j\left(\mod \operatorname{ord}_{m} a\right)$.
\end{solution}

\begin{exercise}
设 $g$ 为模 $m$ 原根， 证明： $g^{k}$ 为原根当且仅当 $(k, \varphi(m))=1$.
\end{exercise}

\begin{solution}
  $g^k$亦为原根当且仅当$\ord_m(g^k)=\ord_m(g)$.
  而我们知道
  \[
    \ord_m(g^k)=\frac{\ord_m(g)}{(k, \ord_m(g))}.
  \]
  显然有$g^{k}$ 为原根当且仅当 $(k, \varphi(m))=1$.
\end{solution}

\begin{exercise}
设 $p$ 为素数， $d \mid(p-1)$. 证明： $X^{d}-1$ 恰有 $d$ 个根在 $\mathbb{F}_{p}$ 中。
\end{exercise}

\begin{solution}
  既然$d\mid (p-1)$,
由定理1的证明知$\FF_p^*$为$p-1$阶循环群，且恰有一个$d$阶子群，其元素由$x^d-1$的根构成。
\end{solution}



\section{模 $2^{s}$ 分解}



\begin{exercise}
(1) 求整数 $g$ 使其为模 $5^{k}$ 的原根 (对任意 $k \geqslant 1$ ). (2) 求模 $10$ 的原根。 (3) 求模 $50$ 的原根。
\end{exercise}

\begin{solution}
  \begin{enumerate}
    \item 模$5$的所有原根为$2,3$. 由于$2^4=16\nequiv 1\left( \mod 5^2 \right)$,
      由\S3.2中系1知$2$为模$5^k$原根，对任意的$k\geqslant 1$.
由于$3^4\equiv 6\nequiv 1\left( \mod 5^2 \right)$, $3$也是模$5^k$原根。
\item $2$为模$5$原根，由\S3.2中系1知$2+5=7$为模$10$原根。
  所有的模$10$原根为$7^k$, 其中$1\leqslant k<\varphi(10)=4$且$(k, \varphi(10))=1$.
  因此所有模$10$原根为$7, 7^3\equiv 3$.
\item \fangfa{1} $3$为模$5^2$原根，由\S3.2中系1知$3$为模$50$原根。
所有的模$50$原根为$3^k$, 其中$1\leqslant k<\varphi(50)=20$且$(k, \varphi(50))=1$.
因此所有模$50$原根为
\[
  3, 3^3\equiv 27, 3^7\equiv 37, 3^9\equiv 33, 3^{11}\equiv 47, 3^{13}\equiv 23, 3^{17}\equiv 13, 3^{19}\equiv  17.
\]

  \fangfa{2} $2$为模$5^2$原根，由\S3.2中系1知$2+5^2=27$为模$50$原根。
所有的模$50$原根为$27^k$, 其中$1\leqslant k<\varphi(50)=20$且$(k, \varphi(50))=1$.
因此所有模$50$原根为
\[
  27, 27^3\equiv 33, 27^7\equiv 3, 27^9\equiv 37, 27^{11}\equiv 23, 27^{13}\equiv 17, 27^{17}\equiv 47, 27^{19}\equiv  13.
\tag*{\qedhere}
\]
  \end{enumerate}
\end{solution}

\begin{exercise}
  令 $p$ 为奇素数， $p \nmid a$, $a \neq\pm 1$,
  且$a$ 模 $p$ 的阶为 $d$.
  证明:
\begin{enumerate}
\item  存在最大正整数 $k_{0}$使得 $a^{d} \equiv 1\left(\mod p^{k_{0}}\right)$成立。
\item  $\ord_{p^k}(a)=\begin{cases}
    d, & \text{当~}k \leqslant k_{0},\\
    d p^{k-k_{0}}, & \text{当~}k>k_{0}.
  \end{cases}$.
  \end{enumerate}
\end{exercise}

\begin{solution}
 \begin{enumerate}
   \item 假设对任意的正整数$k$有$a^{d} \equiv 1\left(\mod p^{k}\right)$.
     那么$p^k\mid a^d-1$, 对任意$k$.
     这样必有$a^d-1=0$. 这样$a=\pm 1$. 这与假设矛盾了。
\item 
    我们先证明$k\leqslant k_0$时$\ord_{p^k}(a)=d$. 
      令$s=\ord_{p^k}(a)$. 由$k_0$的最大性知$a^d\equiv 1\left( \mod p^k \right)$.
      故$s\mid d$. 同时，该式也表明$a^d\equiv 1\left( \mod p \right)$.
      因此$d=\ord_p(a)\mid s$. 这样$s=d$.

      现在设$k\geqslant k_0$. 要证明$\ord_{p^k}(a)=dp^{k-k_0}$, 
      我们断言
      \begin{equation}\label{3.3.1}
        a^{dp^{k-k_0}} = 1+ cp^{k},\quad \text{其中~} p\nmid c.
      \end{equation}
      由~\eqref{3.3.1}, 我们有
      \[
        a^{dp^{k-k_0}}\equiv 1\left( \mod p^k \right), \quad 
        a^{dp^{k-1-k_0}}\nequiv 1\left( \mod p^k \right),
      \]
      因此$\ord_{p^k}(a)=dp^{k-k_0}$.
      我们对$k$归纳来证明~\eqref{3.3.1}。考虑$k=k_0$. 我们有
      \[
        a^d\equiv 1\left( \mod p^{k_0} \right), \quad 
        a^d\nequiv 1\left( \mod p^{k_0+1} \right).
      \]
      因此$a^d=1+cp^{k_0}$, 其中$p\nmid c$.
      再考虑$k>k_0$. 由归纳假设
$a^{dp^{k-1-k_0}} = 1+ cp^{k-1}$, 其中$p\nmid c$.
两边取$p$次方得
\begin{align}
  a^{dp^{k-k_0}}&= (1+ cp^{k-1})^p \notag\\
  &= 1+\binom{p}{1} cp^{k-1} + \binom{p}{2} (cp^{k-1} )^2+ \cdots + \binom{p}{p-1} (cp^{k-1} )^{p-1}+(cp^{k-1})^p \notag\\
  &= 1+cp^k + \binom{p}{2} (cp^{k-1} )^2+ \cdots + \binom{p}{p-1} (cp^{k-1} )^{p-1}+ (cp^{k-1})^p.
  \label{3.3.2}
\end{align}
我们知道$1\leqslant i<p$时$p\mid \binom{p}{i}$. 又$k\geqslant 2$, 
故$2\leqslant i<p$时
\[
  1+i(k-1)\geqslant 1+2(k-1)\geqslant k+1;
\]
因此
此时
$ p^{k+1} \mid \binom{p}{i} (cp^{k-1} )^i.$
亦有$(k-1)p\geqslant k+1$, 因此 
$p^{k+1} \mid (cp^{k-1})^p.$
如此，\eqref{3.3.2}~中除前两项外都能被$p^{k+1}$整除。
而$cp^k$能被$p^k$整除不能被$p^{k+1}$整除，
可知$a^{dp^{k-k_0}} = 1+ c'p^{k}$, 其中$p\nmid c'$. \eqref{3.3.1}~证毕。
          \qedhere
\end{enumerate}
\end{solution}

\begin{exercise}
设如上题。 证明： 若 $k \geqslant k_{0}$ 且 $a^{k} \equiv 1\left(\mod p^{k}\right)$, 则 $\frac{p^{k}}{k}<\frac{a^{d}}{d}$. 从而 $a^{k} \equiv 1\left(\mod p^{k}\right)$ 只有有限多解。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
用上题判断： $9^{k} \equiv 1\left(\mod 7^{k}\right)$ 无解。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
求解 $17^{k} \equiv 1\left(\mod 15^{k}\right)$.
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
求解 $3^{k} \equiv 1\left(\mod 2^{k}\right)$.
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
设 $g$ 为模 $p$ 原根 ( $p$ 为奇素数). 由下式证明 Wilson 定理：
\[
  (p-1)!\equiv g^{(p-1)(p-2) / 2} \equiv-1 \quad \left(\mod p\right).
\]
\end{exercise}

\begin{solution}
  既然$g$为模$p$原根，我们有$\operatorname{ord}_p(g)=p-1$, 且
\[
  U_p=\{\bar{1}, \bar{2},\cdots,\overline{p-1}\}=\{1, \bar{g}, \bar{g}^2, \cdots, \bar{g}^{p-2}\}.
\]
这样
\[
  (p-1)!\equiv g^{\frac{(p-1)(p-2)}{2}}\left( \mod p \right).
\]
由于$p$为奇数，$(p-1)\nmid \frac{(p-1)(p-2)}{2}$, 因此
\[
g^{\frac{(p-1)(p-2)}{2}}\nequiv 1 \left( \mod p \right).
\]
但
\[
  \left( g^{\frac{(p-1)(p-2)}{2}} \right)^2=g^{(p-1)(p-2)} \equiv 1 \left( \mod p \right),
\]
因此
\[
  g^{\frac{(p-1)(p-2)}{ 2}} \equiv-1 \quad \left(\mod p\right).
\]
这里注意到$x^2-1\in \FF_p[x]$的两个根为$\pm 1$.
\end{solution}

\begin{exercise}
证明： (Wolstenholme 定理) 设 $p>3$ 为素数， 则 $1+\frac{1}{2}+\cdots+\frac{1}{p-1}$ 的分子含因子 $p^{2}$ (用新
记号： 记 $a x \equiv 1 \left(\mod m\right)$ 的解为 $a^{-1}$ 或 $\frac{1}{a}$ (当 $\left.(a, m)=1\right)$. 则定理可记为
\[
  1+\frac{1}{2}+\cdots+\frac{1}{p-1} \equiv 0 \quad\left(\mod p^{2}\right).
\]
\end{exercise}

\begin{solution}

\end{solution}

\section{指标与 $n$ 次剩余}




\begin{exercise}\label{求n次剩余}
对 $m=5,7,19,23$ 和 $n=2,3,4,5$, 分别求出模 $m$ 最小原根， 和所有的 $n$ 次剩余。
\end{exercise}

\begin{solution}
  \emph{第一步}：找最小原根。
  \begin{enumerate}
\item $m=5$. $\varphi(5)=4=2^2$. 而
  $4/2=2$,
故需验证 $g^{2}$ 不同余于 $1\left(\mod 23\right)$.

试验 $g=2$ 可否： $2^2\equiv -1\left(\mod 5\right)$. 故 $2$ 为原根。

因此模 $5$ 的最小原根为 $g=2$. 

\item $m=7$. $\varphi(7)=6=2\times 3$. 而
  $6/2=3, 6/3=2$,
  故需验证 $g^{2}, g^3$ 不同余于 $1\left(\mod 7 \right)$.

  试验 $g=2$ 可否： $2^2\equiv 4\left(\mod 7\right)$, $2^3\equiv 1\left(\mod 7\right)$. 
  故 $2$ 非原根。

试验 $g=3$ 可否： $3^2\equiv 2\left(\mod 7\right)$, $3^3\equiv -1\left(\mod 7\right)$. 
  故 $3$ 为原根。

因此模 $7$ 的最小原根为 $g=3$. 

\item $m=19$. $\varphi(19)=18=2\times 3^2$. 而
  $18/2=9, 18/3=6$,
  故需验证 $g^{6}, g^9$ 不同余于 $1\left(\mod 23\right)$.

  试验 $g=2$ 可否： $2^6\equiv 7\left(\mod 19\right)$, $2^9\equiv -1\left(\mod 19\right)$. 故 $2$ 为原根。

因此模 $19$ 的最小原根为 $g=2$. 


    \item $m=23$. $\varphi(23)=22=2\cdot 11$. 而
  $22/2=11$, $22/11=2$,
故需验证 $g^{11}, g^{2}$ 均不同余于 $1\left(\mod 23\right)$.

试验 $g=2$ 可否： $2^{11} \equiv 2048 \equiv 1\left(\mod 23\right)$. 故 $2$ 非原根。

试验 $g=3$ 可否： $3^{11} \equiv 3^{3\times 3+2}\equiv 27^3\cdot 9\equiv 4^3\cdot 9\equiv  -5\times 9\equiv 1\left(\mod 23\right)$. 故 $3$ 非原根。

跳过 $4=2^{2}$. 因 ord $a^{r}=\frac{\operatorname{ord} a}{(r, \operatorname{ord} a)} \leqslant \operatorname{ord} a$, 故 $\operatorname{ord}  2^{2} \leqslant \operatorname{ord} 2$. 见 3.1 引理 5.

试验 $g=5$ 可否： $5^{2} \equiv 2\nequiv 1\left(\mod 23\right)$, 且
\[
  5^{11} \equiv 5^{2\times 5+1}\equiv 25^5\cdot 5\equiv 2^5\cdot 5\equiv 9\cdot 5\equiv -1\nequiv 1\left(\mod 23\right).
\]
故 $5$ 为原根。


因此模 $23$ 的最小原根为 $g=5$. 
  \end{enumerate}

  \emph{第二步}（方法一）：应用定理1中指标条件来确定所有$n$次剩余。
  \begin{enumerate}
    \item $m=5$. 原根$2$如下生成$U_5$:
\begin{center}
  \begin{tabular}{C|C|C|C}
    \hline
  \overline{1} & \overline{2} & \overline{2}^{2} & \overline{2}^{3}  \\
\hline
\overline{1} & \overline{2} & \overline{4} & \overline{3} \\
\hline
\end{tabular}
\end{center}
因 $a$ 为 $n$ 次剩余条件为 $(n, 4) \mid \operatorname{ind} a$. 在 $n=2,3,4,5$ 时依次为
\[
2 \mid \operatorname{ind} a, \quad 1 \mid \operatorname{ind} a, \quad 
4 \mid \operatorname{ind} a, \quad 1\mid \operatorname{ind} a.
\]
故模$5$的 $2$ 次剩余为： $1,4$ (在一个代表元系中， 恰 $\varphi(m) / d=4 / 2$个). $4$次剩余为：$1$.
而所有$U_5$中元素全为 $3$ 次剩余和$5$次剩余。
\item $m=7$. 原根$3$如下生成$U_7$:
\begin{center}
  \begin{tabular}{C|C|C|C|C|C}
    \hline
  \overline{1} & \overline{3} & \overline{3}^{2} & \overline{3}^{3}  & \overline{3}^{4} & \overline{3}^{5} \\
\hline
\overline{1} & \overline{3} & \overline{2} & \overline{6} & \overline{4} & \overline{5}\\
\hline
\end{tabular}
\end{center}
因 $a$ 为 $n$ 次剩余条件为 $(n, 6) \mid \operatorname{ind} a$. 在 $n=2,3,4,5$ 时依次为
\[
2 \mid \operatorname{ind} a, \quad 3 \mid \operatorname{ind} a, \quad 
2 \mid \operatorname{ind} a, \quad 1\mid \operatorname{ind} a.
\]
故模$7$的 $2$ 次和$4$次剩余为： $1,2,4$ (在一个代表元系中， 恰 $\varphi(m) / d=6 / 2$个). 
模$7$的 $3$ 次剩余为： $1,6$. 
而所有$U_7$中元素全为 $5$次剩余。
\item $m=19$. 原根$2$如下生成$U_{19}$:
\begin{center}
  \begin{tabular}{C|C|C|C|C|C|C|C|C}
    \hline
    \overline{1} & \overline{2} & \overline{2}^{2} & \overline{2}^{3} & \overline{2}^{4} & \overline{2}^{5} & \overline{2}^{6} & \overline{2}^{7} & \overline{2}^{8} \\
\hline
\overline{1} & \overline{2} & \overline{4} & \overline{8} & \overline{16} & \overline{13} & \overline{7} & \overline{14} & \overline{9} \\
\hline\hline
\overline{2}^{9} &\overline{2}^{10} & \overline{2}^{11} & \overline{2}^{12} & \overline{2}^{13} & \overline{2}^{14} & \overline{2}^{15} & \overline{2}^{16} & \overline{2}^{17}  \\
\hline
\overline{18}  &
\overline{17} & \overline{15} & \overline{11} & \overline{3} & \overline{6} & \overline{12} & \overline{5} & \overline{10}  \\
\hline
\end{tabular}
\end{center}
因 $a$ 为 $n$ 次剩余条件为 $(n, 18) \mid \operatorname{ind} a$. 在 $n=2,3,4,5$ 时依次为
\[
2 \mid \operatorname{ind} a, 3 \mid \operatorname{ind} a, 2 \mid \operatorname{ind} a, 1 \mid \operatorname{ind} a.
\]
故 $2$ (和 $4$) 次剩余者为： $1,4,16,7,9,17,11,6,5$ (在一个代表元系中， 恰 $\varphi(m) / d=18 / 2=9$个). 
$3$ 次剩余为 $1,8,7,18,11,12$ (恰 $18 / 3=6$ 个). 
而所有$U_{19}$中元素全为 $5$ 次剩余。

\item $m=23$. 原根$5$如下生成$U_{23}$:
\begin{center}
  \begin{tabular}{C|C|C|C|C|C|C|C|C|C|C}
    \hline
    \overline{1} & \overline{5} & \overline{5}^{2} & \overline{5}^{3} & \overline{5}^{4} & \overline{5}^{5} & \overline{5}^{6} & \overline{5}^{7} & \overline{5}^{8}  & \overline{5}^{9} &\overline{5}^{10}\\
\hline
\overline{1} & \overline{5} & \overline{2} & \overline{10} & \overline{4} & \overline{20} & \overline{8} & \overline{17} & \overline{16} & \overline{11} & \overline{9}  \\
\hline\hline
  \overline{5}^{11} & \overline{5}^{12} & \overline{5}^{13} & \overline{5}^{14} & \overline{5}^{15} & \overline{5}^{16} & \overline{5}^{17}   & \overline{5}^{18} & \overline{5}^{19} & \overline{5}^{20} & \overline{5}^{21}  \\
\hline
 \overline{22} & \overline{18} & \overline{21} & \overline{13} & \overline{19} & \overline{3} & \overline{15} & \overline{6} & \overline{7} & \overline{12}  & \overline{14}\\
\hline
\end{tabular}
\end{center}
因 $a$ 为 $n$ 次剩余条件为 $(n, 22) \mid \operatorname{ind} a$. 在 $n=2,3,4,5$ 时依次为
\[
2 \mid \operatorname{ind} a, 1 \mid \operatorname{ind} a, 2 \mid \operatorname{ind} a, 1 \mid \operatorname{ind} a.
\]
故 $2$ 次和 $4$ 次剩余为： $1,2,4,8,16,9,18,13,3,6,12$ (在一个代表元系中， 恰 $\varphi(m) / d=22/ 2=11$个). 
而所有$U_{23}$中元素全为 $3$次剩余和$5$ 次剩余。
  \end{enumerate}

  \emph{第二步}（方法二）：通过计算所有$U_m$中元素的$n$次方来确定所有$n$次剩余。除了手算，还可以通过SageMath计算。如下函数实现了计算$U_m$中$n$次剩余集：
\begin{minted}[texcl]{sage}
sage: def all_n_th_power(m, n):  # 求所有的模$m$的$n$次剩余
....:     R = IntegerModRing(m)
....:     all = []
....:     for i in range(1, m):
....:         if Integer(i).gcd(m) == 1:
....:             all.append(R(i)^n)
....:     print(set(all))
....: 
\end{minted}
  以$m=5, 23$为例：
\begin{minted}[texcl]{sage}
sage: all_n_th_power(5, 2); all_n_th_power(5, 3); all_n_th_power(5, 4); all_n_th_power(5, 5)
{1, 4}
{1, 2, 3, 4}
{1}
{1, 2, 3, 4}
sage: all_n_th_power(23, 2);all_n_th_power(23,3);all_n_th_power(23,4);all_n_th_power(23,5)
{1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18}
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}
{1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18}
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}
\end{minted}
\end{solution}

\begin{exercise}
  设 $m=41^{2}, 2 \cdot 41^{2}$, 求模 $m$ 最小原根，描述$2$ 次剩余， $3$ 次剩余。
\end{exercise}

\begin{solution}
  %\emph{第一步}：求最小原根。
  \begin{enumerate}
   \item $m=41^2$. $\varphi(41^2)=41\times 40=2^3\cdot 5 \cdot 41$. 而
     $\varphi(41^2)/2=41\times 20$, $\varphi(41^2)/5=41\times 8$,
     $\varphi(41^2)/41=40$,
     故需验证 $g^{40}, g^{41\times 8}, g^{41\times 20}$ 均不同余于 $1\left(\mod 41^2\right)$. 这些计算可借助SageMath完成（手算比较费时）。

试验 $g=2$ 可否： $2^{41\times 20} \equiv 1 \left(\mod 41^2\right)$. 故 $2$ 非原根。

试验 $g=3$ 可否： $3^{41\times 8}  \equiv 1\left(\mod 41^2\right)$. 故 $3$ 非原根。

跳过 $4=2^{2}$. $2$非原根，$4$更不会是。诚然，由$\ord a^{r}=\frac{\operatorname{ord} a}{(r, \operatorname{ord} a)} \leqslant \operatorname{ord} a$知$\operatorname{ord}  2^{2} \leqslant \operatorname{ord} 2$. 

试验 $g=5$ 可否： $5^{41\times 20} \equiv 1\left(\mod 41^2\right)$.
故 $5$ 非原根。

试验 $g=6$ 可否：$6^{40}\equiv 124, 6^{41\times 8}\equiv 51, 6^{41\times 20}\equiv 1680\left( \mod 41^2 \right)$.
故 $6$ 为原根。

因此模 $41^2$ 的最小原根为 $g=6$. 

由于$(2, \varphi(m))= 2$, 由定理1知 $\bar{a}\in U_m$为$2$次剩余当且仅当$2\mid \ind(a)$.
从而所有$2$次剩余为
\[
  6^0, 6^2, 6^4, \cdots, 6^{41\times 40-4}, 6^{41\times 40-2}\left( \mod 41^2 \right).
\]

由于$(3, \varphi(m))= 1$, 由定理1知 $\bar{a}\in U_m$为$3$次剩余当且仅当$1\mid \ind(a)$.
因此所有$U_{41^2}$中元素都是$3$次剩余。

    \item $m=2\times 41^2$. $\varphi(2\times 41^2)=41\times 40=2^3\cdot 5 \cdot 41$. 而
     $\varphi(m)/2=41\times 20$, $\varphi(m)/5=41\times 8$,
     $\varphi(m)/41=40$,
     故需验证 $g^{40}, g^{41\times 8}, g^{41\times 20}$ 均不同余于 $1\left(\mod 2\times 41^2\right)$. 
     这些计算可借助SageMath完成（手算比较费时）。

试验 $g=3$ 可否： $3^{41\times 8}  \equiv 1\left(\mod 2\times 41^2\right)$. 故 $3$ 非原根。

试验 $g=5$ 可否： $5^{41\times 20} \equiv 1\left(\mod 2\times 41^2\right)$.
故 $5$ 非原根。

试验 $g=7$ 可否：$7^{40}\equiv 3199, 6^{41\times 8}\equiv 857, 6^{41\times 20}\equiv 3361\left( \mod 2\times 41^2 \right)$.
故 $7$ 为原根。

因此模 $2\times 41^2$ 的最小原根为 $g=7$. 

由于$(2, \varphi(m))= 2$, 由定理1知 $\bar{a}\in U_m$为$2$次剩余当且仅当$2\mid \ind(a)$.
从而所有$2$次剩余为
\[
  7^0, 7^2, 7^4, \cdots, 7^{41\times 40-4}, 7^{41\times 40-2}\left( \mod 2\times 41^2 \right).
\]

由于$(3, \varphi(m))= 1$, 由定理1知 $\bar{a}\in U_m$为$3$次剩余当且仅当$1\mid \ind(a)$.
因此所有$U_{2\times 41^2}$中元素都是$3$次剩余。
\qedhere
  \end{enumerate}
\end{solution}

\begin{exercise}
证明 $10$ 是模 $17$ 的原根。 由此证明， 在 $1 / 17$ 化为循环小数时， 循环节的长度为 $16$.
\end{exercise}

\begin{solution}
$\ord_{17}(10)\mid \varphi(17)=16$. 
  我们有$10^{2}\equiv -2 \left( \mod 17 \right)$,
  $10^{4}\equiv 4 \left( \mod 17 \right)$,
  $10^{8}\equiv -1 \left( \mod 17 \right)$,
  $10^{16}\equiv 1 \left( \mod 17 \right)$.
  故$\ord_{17}(10)=16$.
这样，$\frac{1}{17}$作为循环小数的循环节的长度为$16$.
参见\S3.1 练习~\ref{1/a的循环节长度}.
\end{solution}

\begin{exercise}
求 $10$ 模 $13$ 的阶 (周期), 和 $1 / 13$ 化为循环小数后循环节的长度有何关系。
\end{exercise}

\begin{solution}
  $\ord_{13}(10)\mid \varphi(13)=12$. 
  我们有$10^{2}\equiv 9\left( \mod 13 \right)$, 
  $10^{3}\equiv -1\left( \mod 13 \right)$,
  $10^{6}\equiv 1\left( \mod 13 \right)$. 
  因此$\ord_{13}(10)=6$. 这样，$\frac{1}{13}$作为循环小数的循环节的长度为$6$.
  参见\S3.1 练习~\ref{1/a的循环节长度}.
\end{solution}

\begin{exercise}\label{-1的指标}
设模 $m(>2)$ 原根存在， $-1$ 的指标是多少? 与原根有无关系?
\end{exercise}

\begin{solution}
  对任意的模$m$原根$g$, $-1$的指标为$\ind_g(-1)=\frac{\varphi(m)}{2}$. 
  诚然，
  \[
      (g^{\frac{\varphi(m)}{2}})^2 =  g^{\varphi(m)} \equiv 1\left( \mod m \right),\quad \text{但}\quad
      g^{\frac{\varphi(m)}{2}} \nequiv 1\left( \mod m \right),
\]
因此$g^{\frac{\varphi(m)}{2}}\equiv -1\left( \mod m \right)$. 
这样$\ind_g(-1)=\frac{\varphi(m)}{2}$. 
\end{solution}

\begin{exercise}
证明：模 $p$ 原根之积同余于 $(-1)^{\varphi(p-1)} \left(\mod p\right)$.
\end{exercise}

\begin{solution}
  若$p=2$或$3$, 惟一原根为$-1$, 题目中的断言成立。
  设$p>3$. 此时$\varphi(p)=p-1\geqslant 3$. 
  任意原根$g$的阶$p-1$都$\geqslant3$表明$g^2\nequiv 1\left( \mod p \right)$,
  或者说，$g\nequiv g^{-1}\left( \mod p \right)$.
  当然，$g^{-1}$亦为原根。
  这样，所有模$p$原根的乘积中，$g, g^{-1}$恰好消掉了，
  从而所有模$p$原根的乘积为$1\left( \mod p \right)$.
  另外，注意到$p>3$时$\varphi(p-1)$为偶数，所以断言在$p>3$时成立。
\end{solution}

\begin{exercise}
设正整数 $m=p q$ 是某两素数 $p, q$ 之积。 证明 $p, q$ 为如下二次方程之根：
\[
x^{2}-[m+1-\varphi(m)] x+m=0
\]
从而证明了 $m$ 的 Euler函数值 $\varphi(m)$ 决定其因子分解 (这在公开密钥加密通信理论中有应用).
\end{exercise}

\begin{solution}

\end{solution}


\begin{exercise}
  令$p$为奇素数。证明：
\begin{enumerate}
  \item $x^2\equiv -1\left( \mod p \right)$有解当且仅当$p=4k+1$.
  \item $x^4\equiv -1\left( \mod p \right)$有解当且仅当$p=8k+1$.
  \end{enumerate}
\end{exercise}

\begin{solution} 令$g$为模$p$原根。由练习~\ref{-1的指标}~知$\ind(-1)=\frac{p-1}{2}$.
  \begin{enumerate}
    \item 由定理1知$x^2\equiv -1\left( \mod p \right)$有解当且仅当
      $2=(2,p-1)\mid \ind(-1)=\frac{p-1}{2}$, 亦即$p=4k+1$.
    \item 由定理1知$x^4\equiv -1\left( \mod p \right)$有解当且仅当
      $(4,p-1)\mid \ind(-1)=\frac{p-1}{2}$. 
      $2\mid (4,p-1)$表明$p=4l+1$. 故$(4,p-1)=4$. 
      故$(4,p-1)\mid \frac{p-1}{2}$当且仅当$p=8k+1$.
      从而$x^4\equiv -1\left( \mod p \right)$有解当且仅当$p=8k+1$.
      \qedhere
  \end{enumerate}
\end{solution}


\section{高次同余式}



\begin{exercise}\label{x^7=1(mod29)}
解同余式： $1+x+x^{2}+\cdots+x^{6} \equiv 0 \left(\mod 29\right)$.
\end{exercise}

\begin{solution}
  $x^7-1\in \FF_{29}[x]$有分解
  \[
    x^7-1=(x-1)(x^6+\cdots+x^2+x+1).
  \]
易知$1+x+x^{2}+\cdots+x^{6} \equiv 0 \left(\mod 29\right)$相当于
$x^7\equiv 1\left( \mod 29 \right)$且$x\nequiv 1\left( \mod 29 \right)$.
我们来解$x^7\equiv 1\left( \mod 29 \right)$.
容易发现$2$为模$29$的最小原根。
注意到$7\mid \varphi(29)=28$.
显然$x^7\equiv 1\left( \mod 29 \right)$相当于$x$的指标$y=\ind_2(x)$能被$4=28/7$整除。
这样
\[
  y= 0, 4, 8, 12, 16, 20, 24.
\]
从而$x^7\equiv 1\left( \mod 29 \right)$的所有解为
\[
  x\equiv 2^y\equiv 1, 16, 24, 7, 25, 23, 20 \left( \mod 29 \right).
\]
故$1+x+x^{2}+\cdots+x^{6} \equiv 0 \left(\mod 29\right)$的所有解为
\[\tag*{\qedhere}
  x\equiv 16, 24, 7, 25, 23, 20 \left( \mod 29 \right).
\]
\end{solution}

\begin{exercise}
将 $x^{2}-2=0$ ($p=7$) 的解 $x_{0}^{\prime}=4$ 提升为模 $7^{s}$ 的解 $(s=2,3,4,5)$.
\end{exercise}

令$f(x)=x^2-2$. 由Hensel引理知存在惟一的整数$a_0, a_1, a_2, \cdots $  ($0\leqslant a_i < p$)
使得提升得到的$f(x)\equiv 0\left( \mod p^s \right)$的解$x_{s-1}$为
  \[
    x_{s-1}=a_0+a_1p+\cdots+ a_{s-1}p^{s-1}.
  \]

\begin{solution}[解答一]
考虑$x^{2}-2=0\left(\mod 7\right)$
的解 $x_{0}= 4$. 
设$x_1=x_{0}+a_{1} p$为
$x^{2}-2=0\left(\mod 7^{2}\right)$
的解。亦即
\[
  0 \equiv x_1^{2}-2 \equiv x_{0}^{2}-2+2 x_{0} a_{1} p \equiv 14+8 a_{1} 7 \quad\left(\mod 7^{2}\right),
\]
可化为 
  $0 \equiv 2+a_{1}\left(\mod 7\right),$
  故$a_1\equiv 5\left( \mod 7 \right)$. 从而得$x^{2}-2=0\left(\mod 7^{2}\right)$的解 
\[
  x_{1}=4+5\cdot 7.
\]
设$x_2=x_{1}+a_{2} p^2$为
$x^{2}-2=0\left(\mod 7^{3}\right)$
的解。亦即
\[
  0 \equiv x_2^{2}-2 \equiv x_{1}^{2}-2+2 x_{1} a_{2} p^2 \equiv 1519+78  a_{1} 7^2 \quad\left(\mod 7^{3}\right),
\]
可化为 
  $0 \equiv 31+a_{1}\left(\mod 7\right),$
  故$a_1\equiv 4\left( \mod 7 \right)$. 从而得$x^{2}-2=0\left(\mod 7^{3}\right)$的解 
\[
  x_{2}=4+5\cdot 7+4\cdot 7^2.
\]
类似地，可提升得模 $7^{4}$ 的解 
\[
  x_{3}=4+5\cdot 7+4 \cdot 7^{2},
\]
模 $7^{5}$ 的解 
\[\tag*{\qedhere}
  x_{4}=4+5\cdot 7+4 \cdot 7^{2}+5 \cdot 7^{4}.
\]
\end{solution}
\begin{solution}[解答二]
从Hensel引理的证明我们得到了公式
  \[
    x_{s}\equiv x_{s-1} -\frac{f(x_{s-1})}{f'(x_{s-1})}\left( \mod p^{s+1} \right),
  \]
其中$1/f'(x_{s-1})$是$f'(x_{s-1})\left( \mod p \right)$的逆。 
本题中$p=7, f=x^2-2, f'=2x, x_0=4$, 从而
\[
  f'(x_0)=8\equiv 1\left( \mod 7 \right),\quad
  1/f'(x_{0})\equiv 1\left( \mod 7 \right).
\]
由于提升得到的$f(x)\equiv 0\left( \mod p^s \right)$的解$x_{s-1}$
满足$x_{s-1}\equiv x_0\left( \mod 7 \right)$, 有
\[
  1/f'(x_{s-1})\equiv 1/f'(x_0)\equiv 1\left( \mod 7 \right).
\]
应用公式可知
\begin{align*}
  x_1&= x_0-f(x_0)/f'(x_0)\equiv x_0-14\equiv  4+5\cdot 7\left( \mod 7^2 \right),\\
x_2&= x_1-f(x_1)/f'(x_1)\equiv x_1-1519\equiv  4+5\cdot 7+4\cdot 7^2\left( \mod 7^3 \right),\\
x_3 &= x_2-f(x_2)/f'(x_2)\equiv x_2-55223\equiv   4+5\cdot 7+4\cdot 7^2\left( \mod 7^4 \right),\\
x_4&= x_4 -f(x_3)/f'(x_3)\equiv x_3-55223\equiv  4+5\cdot 7+4\cdot 7^2+5\cdot 7^4\left( \mod 7^5 \right).
\tag*{\qedhere}
\end{align*}
\end{solution}

\begin{exercise}
求解 $x^{3} \equiv 1 \left(\mod 19\right), x^{4} \equiv 1 \left(\mod 19\right)$.
\end{exercise}

\begin{solution} 容易发现$2$为模$29$的最小原根。显然$\ind(1)=0$.
  \begin{enumerate}
    \item  注意到$3\mid \varphi(19)=18$. 
显然$x^3\equiv 1\left( \mod 19 \right)$相当于$x$的指标$y=\ind_2(x)$能被$6=18/3$整除。
这样
\[
  y = 0, 6, 12.
\]
从而$x^3\equiv 1\left( \mod 19 \right)$的所有解为
\[
  x\equiv 2^y\equiv 1, 7, 11 \left( \mod 19 \right).
\]
\item 由\S3.4的证明知解$x$的指标$y$满足方程
\[
  4y\equiv 0\left( \mod \varphi(19) \right).
\]
因此$2y\equiv 0\left( \mod 9 \right)$, $y\equiv 0\left( \mod 9 \right)$.
这样
\[
  y\equiv 0, 9 \left( \mod 18 \right).
\]
从而$x^4\equiv 1\left( \mod 19 \right)$的所有解为
\[\tag*{\qedhere}
  x\equiv 2^y\equiv 1, -1 \left( \mod 19 \right).
\]
  \end{enumerate}
\end{solution}

\begin{exercise}
利用原根和指标求解 $x^{7} \equiv 1 \left(\mod 29\right)$.
\end{exercise}

\begin{solution}
  见练习~\ref{x^7=1(mod29)}.
\end{solution}

\begin{exercise}
求 $a$ 使 $x^{3} \equiv a \left(\mod p\right)$ 有解 (对 $p=5,7,11,13$, $p\nmid a$).
\end{exercise}

\begin{solution}
  可如习题3.4练习~\ref{求n次剩余}~中计算。实际上，模$5$的$3$次剩余为$U_5$中所有元素；
  模$7$的$3$次剩余为$1,6$;
  模$11$的$3$次剩余为$U_{11}$中所有元素；
  模$13$的$3$次剩余为$1,5,8,12$.
\end{solution}


\begin{exercise}
设 $a$ 模 $p$ 的阶为 $3$, 证明： $1+a$ 的阶为 $6$.
\end{exercise}

\begin{solution}
  显然$p>2$, 否则$U_p$中没有$3$阶元素。
  $a^3\equiv 1\left( \mod p \right)$表明$a^2+a+1\equiv 0\left( \mod p \right)$ (显然$a\nequiv 1\left( \mod p \right)$).
  这样$1+a\equiv -a^2\left( \mod p \right)$.
  故
  \[
    (1+a)^3\equiv (-a^2)^3\equiv -1\nequiv 1\left( \mod p \right),\quad
    (1+a)^6\equiv (-a^2)^6\equiv 1\left( \mod p \right).
  \]
  而且，
  \[
    (1+a)^2=a^2+2a+1\equiv a\nequiv 1\left( \mod p \right).
  \]
  综上可知，$\ord_p(1+a)=6$.
\end{solution}

\begin{exercise}
证明： 同余式 $f(x)=x^{p-1}-1 \equiv 0\left(\mod p^{s}\right)$ 恰有 $p-1$ 个根 (对任一$s$), 从而有 $p-1$ 个 $p$-adic数解。
\end{exercise}

\begin{solution}
  $x^{p-1}-1\left( \mod p \right)$有$p-1$个解$1,2,\cdots,p-1$.
  故由定理2知$x^{p-1}-1\left( \mod p^s \right)$也恰有$p-1$个解。
  由Hensel引理知模$p$解$1,2,\cdots,p-1$中每个都惟一地延拓为一个$p$-进制解，
  故有$p-1$个$p$-进制解。
\end{solution}


\begin{exercise}[Hensel 引理拓展]
\starmark
证明： 设 $p$ 为素数， $f(x)$ 为整系数多项式 (首项系数不被 $p$ 整除).方程 $f(x)=0$ 模 $p^{s}$ 的任意解 $x_{1}$ 都是由方程 $f(x)=0$ 模 $p^{s-1}$ 的某解 $x_{0}$ “提升” 得到的 (即 $x_{1}=x_{0}+$ $c p^{s-1}$, 且可设 $0 \leqslant x_{0}<p^{s-1}, 0 \leqslant x_{1}<p^{s}, 0 \leqslant c<p, s \geqslant 2$ ). 方程模 $p^{s-1}$ 的每一解 $x_{0}$ 可提升为模 $p^{s}$的 $r_{s}$ 个解， 其中
\[
  r_{s}= \begin{cases}1, & \text {若 $f^{\prime}\left(x_{0}\right) \neq 0 \left(\mod p\right)$;} \\ p, & \text {若 $f^{\prime}\left(x_{0}\right) \equiv 0 \left(\mod p\right), x_{0}$ 是此方程模 $p^{s}$ 根；} \\ 0, & \text {若  $f^{\prime}\left(x_{0}\right) \equiv 0 \left(\mod p\right), x_{0}$ 不是此方程模 $p^{s}$  根。 }\end{cases}
\]
特别可知， 当 $f^{\prime}(x)$ 与 $f(x)$ 在 $\mathbb{F}_{p}$ 中没有相同零点时， $f(x)=0$ 模 $p$ 与模 $p^{s}$ 的解数相同， 前者的每个解唯一提升为后者的解 (对任意 $s$ ), 从而唯一提升为 $p$-adic 解。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
  求解 (1) $x^3+x^2+2x+26\equiv 0\left( \mod 343 \right)$. (2) $x^2+x+34\equiv 0\left( \mod 81 \right)$.
\end{exercise}

\begin{solution}
\begin{enumerate}
  \item $343=7^3$. 令$f(x)=x^3+x^2+2x+26$.
     试探可得$f(x)\equiv 0\left( \mod 7 \right)$有唯一解$x_0\equiv 2\left( \mod 7 \right)$.
      我们有
      \[
        f'(x_0)= 18 \equiv 4\nequiv 0\left( \mod 7 \right), \quad
        f'(x_0)^{-1} \equiv 2\left( \mod 7 \right).
      \]
      可应用Hensel引理提升$f(x)$模$7$的解$x_0=2$得$f(x)\equiv 0\left( \mod 49 \right)$的解
      \[
      \begin{aligned}
           x_1 & \equiv x_0-f(x_0)/f'(x_0)
              \equiv -82\equiv 16\left( \mod 49 \right);
            \end{aligned}
    \]
   接着提升$x_1$为$f(x)\equiv 0\left( \mod 343 \right)$的解
   \[
   \begin{aligned}
        x_2& \equiv x_1-f(x_1)/f'(x_1)\equiv x_1-f(x_1)/f'(x_0)\equiv 16-f(16)/f'(2) \\
        & \equiv -8804 \equiv 114\left( \mod 343 \right).
      \end{aligned}
 \]
   因此$f(x)\equiv 0\left( \mod 343 \right)$的唯一解为$x\equiv 114 \left( \mod 343 \right)$.
 \item $81=3^4$. 令$f(x)=x^3+x+34$. 试探可得
   $f(x)\equiv 0\left( \mod 3 \right)$有唯一解$x_0\equiv 1 \left( \mod 3 \right)$.
   我们有
      \[
        f'(x_0)= 1 \nequiv 0\left( \mod 3 \right), \quad
        f'(x_0)^{-1} \equiv 1\left( \mod 3 \right).
      \]
      可应用Hensel引理提升$f(x)$模$3$的解$x_0=1$得唯一的
      $f(x)\equiv 0\left( \mod p^{s+1} \right)$的解$x_s$.
      我们有
      \[
        \begin{aligned}
          x_1& \equiv x_0-f(x_0)/f'(x_0)
          \equiv -35\equiv 1\left( \mod 9 \right),\\
x_2& \equiv x_1-f(x_1)/f'(x_0)
          \equiv -35\equiv 19\left( \mod 27 \right),\\
x_3& \equiv x_2-f(x_2)/f'(x_0)
\equiv -6893\equiv 73\left( \mod 81 \right).
        \end{aligned}
      \]
      因此$f(x)\equiv 0\left( \mod 81 \right)$的唯一解为$x\equiv 73\left( \mod 81 \right)$.
      \qedhere
 \end{enumerate}
\end{solution}


\section{Möbius 反演与数论函数}




\begin{exercise}
证明正文表中函数 $\lambda$ 和 $s$ 的断言。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
证明：Dirichlet 卷积对普通加法满足分配律。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
由 Euler 函数计算公式证明素数有无限多。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
定义 $\sigma_{k}(n)=\sum_{d \mid n} d^{k}$, 其中$k$为非负整数。
证明 $\sigma_{k}$ 为积性函数， 试给出其计算公式。
\end{exercise}

\begin{solution}
  令$n=p_1^{e_1}\cdots p_s^{e_s}$, 其中$p_1,\cdots,p_s$为互异的素数，
  $e_1,\cdots,e_s$为非负整数。我们有
\[
\begin{aligned}
  \sigma_k(p_1^{e_1}\cdots p_s^{e_s})&= 
  \sum_{0\leqslant k_i \leqslant e_i} \left( p_1^{k_1}\cdots p_s^{k_s} \right)^k = \sum_{0\leqslant k_i \leqslant e_i}  (p_1^k)^{k_1}\cdots (p_s^k)^{k_s} \\
  &= \left( (p_1^k)^0 + \cdots + (p_1^k)^{e_1} \right) \cdots \left( (p_s^k)^0 + \cdots + (p_s^k)^{e_s} \right)\\
  &= \frac{p_1^{k(e_1+1)}-1}{p_1^k-1} \cdots \frac{p_s^{k(e_s+1)}-1}{p_s^k-1}.
\end{aligned}
\]
取$s=1$知对素数$p$和非负整数$e$有$\sigma_k(p^e)=\frac{p^{k(e+1)}-1}{p^k-1}$ (若$k=0$, 这是$e+1$). 因此
\[
  \sigma_k(p_1^{e_1}\cdots p_s^{e_s}) = \sigma_k(p_1^{e_1}) \cdots \sigma_k(p_s^{e_s}).
\]
这样，由引理2中积性函数的刻画知$\sigma_k$为积性函数。
\end{solution}

\begin{exercise}
若 $f$ 为积性函数， 证明 $h(n)=\sum_{d \mid n} \mu(n / d) f(d)$ 也是积性函数; 从而推知任一积性函数是某积性函数的 “求和函数”。
\end{exercise}

\begin{solution}
  我们有$h=\mu*f$. 由于$\mu, f$都是积性函数，它们的 Dirichlet 卷积也是 (定理2(1)).
  由$h=\mu*f$知$f=1*h=\sigma_{/h}$, 即$f$为积性函数$h$的求和函数。
\end{solution}

\begin{exercise}
正整数 $n$ 称为完全数 (perfect number) 是指 $n$ 等于其真因子 (即非自身的正因子)之和， 即 $n=\sigma_{1}(n)-n$, 亦即 $\sigma_{1}(n)=2 n$. 例如 $6=1+2+3$, 故 $6$ 是完全数。 证明：
\begin{enumerate}[(1)]
\item 若 $n=2^{p-1}\left(2^{p}-1\right), p$ 和 $M_{p}=2^{p}-1$ 为素数， 则 $n$ 是完全数。

\item%(2)
若偶数 $n$ 是完全数， 则 $n$ 为 (1) 中形式。
\end{enumerate}
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
  [Möbius 反演---座位模式] 设有 $n$ 个座位环绕圆桌， 每位可坐一女或一男， 分别以 $0$ 或 $1$ 表示。 故有 $2^{n}$ 个就座模式， 每个模式对应于一个长为 $n$ 的 $0,1$ 字符串。 若人们顺次转动 $d$ 个座位 (取最小的 $d$ ) 而模式不变， 则称该模式有周期 $d$ (相当于说， 此模式可通过顺次转位生出 $d$ 个不同模式。 我们称这 $d$ 个模式是等价的， 因为人们的相对位置没变).

试求周期为 $d$ 的模式个数 $f(d)$. 再求互不等价的模式总数 $h(n)$. 以 $n=4$ 例证。
\end{exercise}

\begin{solution}

\end{solution}

\begin{exercise}
Mangoldt (曼戈尔特) 函数 $\Lambda$ 定义为 $\Lambda\left(p^{k}\right)=\log p, \Lambda(n)=0$ (当 $n \neq p^{k}$), 其中 $p$ 为素数， $k$ 为正整数， $\log x=\log _{e} x$. 证明 $\sum_{d \mid n} \Lambda(d)=\log n$, 并得出
\[
  \Lambda(n)=\sum_{d \mid n} \log (d) \mu(n / d)=-\sum_{d \mid n} \log (d) \mu(d).
\]
\end{exercise}

\begin{solution}
    令$n$的素分解为$n=\prod_{i=1}^t p_i^{r_i}$. 那么我们有
    \[
      \begin{aligned}
        \sum_{d \mid n} \Lambda(d)&= 
        \sum_{i=1}^t \sum_{j=1}^{r_i} \Lambda(p_i^{k_i}) = 
        \sum_{i=1}^t r_i \log p_i \\
        &= \sum_{i=1}^t \log p_i^{r_i} = \log n,
      \end{aligned}
    \]
    即$\sum_{d \mid n} \Lambda(d)=\log n$.
    应用M\"obius反演可知
    $\Lambda(n)=\sum_{d \mid n}  \mu(\frac{n}{d})\log (d).$
    而且，
      \begin{align*}
        \Lambda(n)&= \sum_{d \mid n}  \mu(d)\log (\frac{n}{d})
        = \sum_{d \mid n}  \mu(d)(\log n-\log d)\\
        &= \log n \sum_{d \mid n}  \mu(d) - \sum_{d \mid n}  \mu(d)\log d\\
        &= \log(n) \varepsilon(n) - \sum_{d \mid n}  \mu(d)\log d\\
        &= - \sum_{d \mid n}  \mu(d)\log d.
        \tag*{\qedhere}
      \end{align*}
\end{solution}

\begin{exercise}[Gauss]
证明：模 $p$ 原根之和同余于 $\mu(p-1) \left(\mod p\right)$ ( $\mu$ 为 Möbius $\mu$ 函数).
\end{exercise}

\begin{solution}

\end{solution}


